package com.dragon.datastructure.linkedlist;

/**
 * Josephu(约瑟夫、约瑟夫环) 问题
 * <p>
 * 设编号为 1，2，... n 的 n 个人围坐一圈，约定编号为 k(1<=k<=n)的人从 1 开始报数，数 到 m 的那个人出列，
 * 它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由 此产生一个出队编号的序列。
 *
 * @author dragon
 * @since 2019/12/19
 */
public class Test6 {

    public static void main(String[] args) {
        int luckyNumber = getLuckyNumber(5, 1, 2);
        System.out.println(luckyNumber);
    }

    /**
     * 得到幸运数字
     *
     * @param totalNumber 总人数
     * @param startNumber 从几号开始
     * @param count       数到count次之后的这个人就出列
     * @return 返回最后一个幸运数字
     */
    public static int getLuckyNumber(int totalNumber, int startNumber, int count) {
        if (totalNumber <= 0 || totalNumber < startNumber || startNumber < 1 || count < 0) {
            throw new IllegalArgumentException("参数有误");
        }
        int[] loop = new int[totalNumber];
        for (int i = 0; i < loop.length; i++) {
            loop[i] = i + 1;
        }
        int killedCount = 0;
        int startIndex = startNumber - 1;
        int countedNum = 0;
        while (true) {
            if (loop[startIndex] != -1) {
                countedNum++;
            }
            if (countedNum == count) {
                System.out.println("被杀的角标:" + startIndex + " 被杀的人的号码:" + loop[startIndex]);
                if (killedCount == (totalNumber - 1)) {
                    return loop[startIndex];
                }
                loop[startIndex] = -1;
                killedCount++;
                countedNum = 0;

            }
            startIndex = (++startIndex) % totalNumber;
        }

    }
}
